This invention relates to the field of computer graphics, and more specifically, to modeling and/or simulating the behavior and motion of real-world articulated objects such as humans, animals and birds in real-time 3-dimensional video games and other interactive contexts. Still more particularly, this invention relates to a unique solution to the problem of efficiently inserting external matrix transformations (e.g., generated in real time) to computer-modeled animations and/or changing animation sequences at an arbitrary point.
Computers and video games have revolutionized animationxe2x80x94the process of showing a sequence of images in rapid succession to create the illusion of motion.
In the past, animations were created by a human artist drawing each of the many still frames required (e.g., over 1000 frames for each minute of animation). Now computers can do most of this work.
For example, computers are commonly used to automatically generate an arbitrarily-long sequence of successive incremental frames between two xe2x80x9ckey framesxe2x80x9d specified by the animation artist or captured by an image sensing device. Using this technique, a first frame and a last frame of an animation sequence are specified, along with the duration of the sequence. Based on this information, the computer automatically generates the many intermediate frames between the first and last frames using a process called interpolation. FIG. 1 illustrates this well known technique. In the FIG. 1 example, the animation artist specifies a first key frame 10 in which the arm of character 11 is lowered, and a second key frame 12 in which character 11""s arm is raised. The computer interpolates to automatically generate intermediate frames 14(1), 14(2), 14(3), . . . , 14(N), showing character 11""s arm in the various intermediate positions between the lowered and raised positions.
Pre-storing each still picture in its entirety would take up too much space. Therefore, the computer uses a sequence of mathematical transformations to specify incremental changes between the successive frames of the animation. These mathematical transformations can be conveniently represented by a mathematical construct called a transformation matrix (xe2x80x9cMxe2x80x9d) that specifies the amount of translation, rotation and scaling in each of the three possible axes (x, y, z) of three-dimensional space. Such transformation matrices are commonly used in computer graphics to represent changes in position, orientation and/or size between successive images.
FIG. 1 shows how a first transformation matrix M 16(1) transforms the beginning key frame 10 to a first intermediate frame 14(1); a second transformation matrix M 16(2) transforms the first intermediate frame 14(1) to a second intermediate frame 14(2); and so on, with a last transformation matrix M 16(N) transforming the last interpolated intermediate frame 14(Nxe2x88x921) to the second key frame 12.
In this example, the computer models character 11 just as real humans or animals are constructedxe2x80x94out of different parts (e.g., legs, arms and a torso) interconnected by articulated joints. See FIG. 1A. This modelling technique allows the computer to break up the animation problem into more easily handled parts (for example, how the character""s right arm moves relative to the character""s torso; and how the character""s torso moves relative to the character""s surroundings). Dividing a character 11 up into different articulated portions allows the computer to use different transformation matrices to move parts of the character relative to other parts of the character. For example, one transformation matrix may be applicable to the entire character (e.g., to move the entire character relative to a common three-dimensional xe2x80x9cworldxe2x80x9d space). Other matrices may apply to various body parts of the character. Such articulated portions are sometimes represented in a hierarchical structure an example of which shown in FIG. 1B. To move a part of the character relative to the rest of the character (e.g., to cause the character to raise its arm), a transformation matrix is applied to that part of the character relative to the rest of the character.
Because the animation must run at high speed (i.e., over a thousand pictures a minute) to create the illusion of fluid motion, it is desirable to pre-compute and pre-store the necessary animation transformation matrices when the animation sequence is authored. Then, during video game play or other presentation of the animation, the computer reads these pre-stored matrices and applies them to achieve a desired visual animation effect.
However, in an interactive situation like a video game, how a character moves and how a scene changes may depend in part on events occurring in real time (for example, a game player""s operation of joysticks, buttons or other controls). This means that the real time interactive animation or simulation cannot rely entirely on pre-computed animation matrices, but must instead provide some way for the animation to also be affected by real world inputs. For example, while a character""s arm and leg motion may be characteristic of the particular character and may be essentially the same irrespective of the direction in which the character walks, the direction in which the character walks may be controlled by operation of a keyboard, handheld controller or joystick.
While it would be desirable to use the same pre-computed animation (matrix) sequences for any arbitrary walking direction, this has sometimes been difficult to achieve in the past because of the way the animation transformation matrices are typically pre-computed as representing the incremental change(s) (xcex94) between successive frames of the animation. This has in some cases meant that the animation artist at authoring time must anticipate each of the various directions the character will be required to walk, and pre-compute a different animation sequence for each different direction. For example, one technique pre-computes a walking animation sequence for each 10 degrees of the compassxe2x80x94allowing a character to walk in any selectable one of thirty-six different directions. Storing all of these various pre-computed sequences takes up a lot of space in memory, and also does not actually cover every possible walking direction (for example, in this scenario, the video game player cannot control the character to walk in a direction of 245 degrees, but is limited to 240 degrees or 250 degrees). It would be desirable to easily and efficiently insert, into a pre-computed animation sequence, an arbitrary external transformation generated in real time response to user interaction in order to, for example, control the character""s orientation and/or translation direction and speed.
Another problem relating to pre-constructed animation matrices for real time interactive animations is how to handle a transition from one animation sequence to another. Past techniques defining each incremental frame of an animation sequence relative to the last frame of the sequence can lead to unnatural-looking transitions between different animation sequences. Suppose for example that during an interactive game, the game player operates a hand controller to cause character 11 to walk for a time and then suddenly pushes a button to cause the character to run. In many prior systems, it was necessary to finish the walking animation sequence before starting the running animation sequence. This is why some prior games noticeably delay transitions between different animation sequences. One approach to solving this problem is to make each animation sequence very short so the player won""t notice any significant delay. In contrast, however, a real world person or animal can immediately change direction or orientation without waiting for a prior motion to complete. It would be desirable to simulate such fluid continuity by allowing an immediate transition from any arbitrary frame of an animation sequence to another animation sequence.
The present invention solves these problems by providing a unique framework for allowing an externally-supplied transformation matrix to further transform an ongoing animation, and for smoothly concatenating animations together seamlessly and arbitrarily. The algorithm can be built in a game-authoring environment that allows artists, musicians and developers to maximize their creative freedom and reduce engineering costs. Techniques provided in accordance with the present invention can be used in the context of a hierarchical articulated system, to efficiently provide lifelike and natural motion of a variety a complex humanoid, animal and other simulated animated objects.
In accordance with one aspect of this invention, a reference object is defined as the root of the articulated system. Transformation matrices describing the motion of this reference object are constrained to translations. This means the matrices can be easily inverted. The ability to easily invert theses matrices avoids the cost of computing, at run time, a xe2x80x9crelativexe2x80x9d matrix representing change relative to the last transformation.
In accordance with another aspect of this invention, a sequence of transformation matrices defines an animation sequence for an articulated part of the reference object. This sequence of transformation matrices is constructed as absolute transformations. That is, the translations described by the transformation matrices are not relative to the previous position of the articulated system, but instead are defined with respect to the origin of the object""s coordinate system. Because each animation step references the origin (as opposed to a xe2x80x9clastxe2x80x9d position), each step is essentially self-containedxe2x80x94and can thus serve as the departure point for any other arbitrary transformation (e.g., the first step of a different animation sequence).
In accordance with a further aspect of the invention, a connection matrix is saved at each animation step to represent the current transformation status of the animated object. This connection matrix embodies the result of the entire history of all previous transformations on the object. This connection matrix is obtained at each animation step by continuously concatenating an external matrix, if any, with the transformation matrix for the animation step. The historical information the connection matrix stores is used to further transform the animation, and is also stored for use in the next successive animation step(s).
Although the transformations performed in accordance with the present invention can be implemented by multiplying the various matrices together to achieve a single transformation matrix which is then applied to the object, one way to think about the transformation process in accordance with one embodiment of the present invention is as follows:
the object is transformed by the inverse translation of the current animation step;
the external transformation (if any) is inserted (e.g., based on real time input);
the object is (re)translated based on the current animation step""s translation matrix;
the connection matrix saved from the last animation step is used to concatenate with above transformation with matrix; and
the next animation step""s transformation matrix is applied to obtain the object""s new location and orientation.
Because these techniques relate the object back to its reference coordinate system origin, they can be efficiently used at any arbitrary point in an animation sequence. This allows any arbitrary frame of an animation sequence to be a departure point for a different animation sequence. Furthermore, because the transformation matrices are defined as absolute translations, the transformation calculations are very efficient (for example, perhaps ten times faster than otherwise in some contexts); and provide a very high degree of natural realism and fluid motion. As one dramatic example, a character that is animated in accordance with the present invention can efficiently and rapidly shift from doing backward handstands to doing forward handstands in a very realistic and fluid manner without interruptions. Furthermore, the calculations provided by the present invention are very inexpensive from a computational standpoint, and are therefore particularly suited for high-speed execution on restricted- resource graphics platforms such as 3D home video game consoles. Such efficiencies also help provide quick prototyping of newly authored animations.
The present invention thus allows an artist to choose a single translation direction (e.g., the most convenient one to model) relative to a reference origin, for authoring a particular animation. The direction of translation and the orientation of the object being animated can be easily and efficiently changed at run-time to any arbitrary orientation and/or translation direction, based on insertion of an external transformation matrix. Furthermore, a connection matrix continuously concatenated with the animation sequence animation matrices can be used to supply a different object location (e.g., based on the object""s prior history in the 3D universe). Still further, the artist may author an animation sequence having any arbitrary duration, since the sequence can be efficiently interrupted at any time in the real-time animation process to bridge into a different animation sequence. These added flexibilities make it possible for a graphics artist without much or any programming experience to easily author extremely realistic and fluid animations.